
"""
652. 寻找重复的子树
"""
from typing import Optional, List

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.dict = {}
        self.res = []

    """
     * 遍历二叉树
     * 思路：要点
     * 1.以我为根的这棵二叉树（子树）长啥样
     *   在后序遍历的地方，记录当前二叉树的节点
     * 2.以其他节点为根的子树都长啥样
     *   每次遍历时，将历次遍历的二叉树以字符串的形式保存，用于比较子树是否重复
    """
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        self.traverse(root)
        return self.res

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode]):
        if not root:
            return '#'
        # 前序位置
        left = self.traverse(root.left)
        # 中序位置
        right = self.traverse(root.right)
        # 后序位置
        my_self = left + ',' + right + ',' + str(root.val)

        if my_self in self.dict:
            if self.dict[my_self] == 0:
                self.res.append(root)
            self.dict[my_self] = self.dict[my_self] + 1
        else:
            self.dict[my_self] = 0
        return my_self